/**
 * 斐波那契数列
 */
public class Solution10 {
     public static long fibonacci1(int n){
         if (n <= 0)
             return 0;

         if (n == 1)
             return 1;

         return fibonacci1(n-1) + fibonacci1(n-2);
     }

     public static long fibonacci2(int n){
         if (n <= 1)
             return n;
         long pre2 = 0, pre1 = 1;
         long fib = 0;
         for (int i = 2; i <= n; i++){
             fib = pre1 + pre2;
             pre2 = pre1;
             pre1 = fib;
         }
         return fib;
     }

//     public static void main(String[] args){
//         System.out.println(fibonacci2(47));
//     }
}
